package com.aqie.arithmetic.datastructure;

import edu.princeton.cs.algs4.Queue;

/**
 * 有序符号表二分查找
 * @param <Key>
 * @param <Value>
 */
public class BinarySearchST<Key extends Comparable<Key>, Value>{
    private Key[] keys;
    private Value[] values;
    private int N;

    public BinarySearchST(int capacity){
        keys   = (Key[])new Comparable[capacity];
        values = (Value[])new Object[capacity];
    }

    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public Value get(Key key){
        if (isEmpty()) return null;
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            return values[i];
        }else {
            return null;
        }
    }

    // 迭代二分查找
    public int rank(Key key){
        int l = 0, h = N - 1;
        while (l <= h){
            int mid = l + (h - l) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0){
                h = mid - 1;
            }else if (cmp > 0){
                l = mid + 1;
            }else{
                return mid;
            }
        }
        return l;
    }

    // 递归二分查找
    public int rank(Key key, int l, int h){
      if (h < l) return l;
      int mid =l + (h - l) / 2;
      int cmp = key.compareTo(keys[mid]);
      if (cmp < 0){
          return rank(key, l, mid - 1);
      }else if (cmp > 0){
          return rank(key, mid + 1, h);
      }else {
          return mid;
      }
    }

    public void put(Key key, Value value){
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0){
            values[i] = value;
            return;
        }
        for (int j = N; j < i; j--){
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }

    public Key min(){
        return keys[0];
    }

    public Key max(){
        return keys[N - 1];
    }

    public Key select(int k){
        return keys[k];
    }


    public Key ceiling(Key key) {
        int i = rank(key);
        return keys[i];
    }

    public Key floor(Key key){
        // 3.1.17 todo
        return null;
    }



    public Key delete(Key key){
        // todo
        return null;
    }

    public void deleteMin(){
        delete(min());
    }

    public void deleteMax(){
        delete(max());
    }

    public int size(Key l, Key h){
        if (h.compareTo(l) < 0) return 0;
        else if (contains(h)){
            return rank(h) - rank(l) + 1;
        }else {
            return rank(h) - rank(l);
        }
    }

    public Iterable<Key> keys(){
        return keys(min(), max());
    }

    public Iterable<Key> keys(Key l, Key h){
        Queue<Key> q = new Queue<>();
        for (int i = rank(l); i < rank(h); i++){
            q.enqueue(keys[i]);
        }
        if (contains(h)){
            q.enqueue(keys[rank(h)]);
        }
        return q;
    }

    private boolean contains(Key key) {
        for (int i = 0; i < N; i++){
            if (keys[i].compareTo(key) == 0) return true;
        }
        return false;
    }
}
